package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/10/20 2:37 PM
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
public class _5_最长回文子串_Manacher {

    public String longestPalindrome(String s) {

        if (s == null) {

            return null;
        }

        if (s.length() == 1) {

            return s;
        }

        char[] sChar = s.toCharArray();

        char[] newChars = prePalindrome(sChar);

        int[] ms = new int[newChars.length];

        int index=0,len = 0,center = 1,rMax = 1;

        for (int i = 2; i < ms.length - 2; i++) {

            int idx = 0;
            if (i < rMax) {

                // 判断以center为中心的左边值加上对应的i
                idx = ms[(center << 1) - i] + i;
                if (idx < rMax) {

                    ms[i] = idx - i;
                    continue;
                }
            }else {

                rMax = i;
            }
            idx = rMax;

            int left = (i << 1) - idx - 1;
            int right = idx + 1;

            while (left >= 0 && right < ms.length && newChars[left] == newChars[right]) {

                left--;
                right++;
            }

            ms[i] = right - 1 - i;

            if (right - 1 >= rMax) {

                rMax = right - 1;
                center = i;
            }

            if (ms[i] > len) {

                len = ms[i];
                index = i;
            }
        }

        int oldIndex = (index - len) >> 1;
        return s.substring(oldIndex,oldIndex+len);
    }

    private char[] prePalindrome(char[] chars) {

        int oldLen = chars.length;
        int newLen = (oldLen << 1) + 3;
        char[] newChars = new char[newLen];

        newChars[0] = '^';

        for (int i = 0; i < oldLen; i++) {

            newChars[(i<<1) + 1] = '#';
            newChars[(i<<1) + 2] = chars[i];
        }

        newChars[newLen - 2] = '#';
        newChars[newLen - 1] = '$';
        return newChars;
    }

}
